/*******************************************************************************
* FileName:         Graph.cpp
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/11/27 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #11
*******************************************************************************/
#include "Graph.h"
#include "limits.h"
#include <iostream>
#include <algorithm>
using namespace std;

Graph::Graph(int max_v): edge_count(0), max_count(max_v), 
adjmax(max_v + 1, vector<int>(max_v + 1, INT_MAX)), father(max_v+ 1, 0){}  //带参构造

Graph::~Graph(){
    // STL类可自动管理内存
}

void Graph::addedge(int s, int t, int w){
    // 防止环的形成
    if(s == t){
        cout << "a circle node is not allowed in this graph" << endl;
        return;
    }
    adjmax[s][t] = w;
    adjmax[t][s] = w;
    EDGE.push_back(edge(s, t, w));
    edge_count++;  //默认没有重复对边赋值
}

int Graph::prim() {
    int n = max_count;
    int res = 0;
    vector<bool> visited(n + 1, false);
    vector<int> dist(n + 1, INT_MAX);

    dist[1] = 0; // 起点到自身的距离为0

     // 总共需要加入 n 个点
    for (int i = 1; i <= n; i++) {
        int temp = INT_MAX, tar = -1;

        // 找到未加入集合 S 中，距离 S 最近的点
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && dist[j] < temp) {
                temp = dist[j];
                tar = j;
            }
        }

        // 如果没有找到点，说明图不连通
        if (tar == -1) return -1;

        // 加入集合 S，更新结果
        visited[tar] = true;
        res += temp;

        // 用新加入的点更新 dist[]
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && adjmax[tar][j] != INT_MAX) {
                dist[j] = min(dist[j], adjmax[tar][j]);
            }
        }
    }
    return res;
}

int Graph::findf(int x){
    if(father[x] == x) return x;
    return father[x] = findf(father[x]);
}

int Graph::kruskal() {
    int n = max_count;
    int m = edge_count;
    int res = 0;
    int visited = 0;

    // 使用 lambda 表达式代替 cmp
    sort(EDGE.begin(), EDGE.end(), [](const edge &e1, const edge &e2) {
        return e1.weigth < e2.weigth;
    });

    // 初始化父节点数组
    for (int i = 1; i <= n; i++) father[i] = i;

    // 遍历所有边
    for (int i = 0; i < m; i++) {
        if (visited == n - 1) break; // 最小生成树完成
        if (findf(EDGE[i].start) == findf(EDGE[i].end)) continue; // 同属一个集合

        // 合并集合，更新结果
        res += EDGE[i].weigth;
        father[findf(EDGE[i].start)] = findf(EDGE[i].end);
        visited++;
    }

    // 如果未达到 n-1 条边，说明图不连通
    if (visited < n - 1) return -1;

    return res;
}
